Năm 1959, các lực lượng biên phòng đổi thành lực lượng Công an nhân dân vũ trang (nay là lực lượng Biên phòng) trực thuộc quyền quản lý của Bộ Công an.

Ngày 28 tháng 7 năm 1956, Thủ tướng Chính phủ ra Nghị định số 982/TTg về việc thành lập Cục Cảnh sát nhân dân thuộc Bộ Công an để thống nhất việc xây dựng, quản lý, huấn luyện, giáo dục các loại cảnh sát nhân dân trong toàn quốc về nghiệp vụ, chính trị, quân sự, văn hoá. Cục trưởng đầu tiên là Thượng tá Lê Hữu Qua[7]

Ngày 20 tháng 7 năm 1962, Chủ tịch Hồ Chí Minh ký lệnh 34-LCT công bố pháp lệnh quy định nhiệm vụ, quyền hạn và pháp lệnh quy định chế độ cấp bậc của sĩ quan và hạ sĩ quan Cảnh sát nhân dân. Để tăng cường kiện toàn bộ máy lực lượng Công an, đồng thời để đáp ứng tình hình và nhiệm vụ cách mạng trong giai đoạn mới.[8]

Ngày 1 tháng 8 năm 1975, kỳ họp thứ 3 Quốc hội khóa X đã quyết định hợp nhất Bộ Công an và Bộ Nội vụ thành một bộ mới lấy tên là Bộ Nội vụ.

Cuối năm 1979, lực lượng Công an nhân dân vũ trang đổi tên là Bộ đội Biên phòng và được chuyển về trực thuộc Bộ Quốc phòng.

Đến năm 1988, Bộ đội Biên phòng lại chuyển sang trực thuộc Bộ Nội vụ, đến cuối năm 1995 thì lại chuyển về Bộ Quốc phòng.

Ngày 7 tháng 5 năm 1998, Quốc hội ra Nghị quyết số 13/1998/NQ-QH10, theo đó Bộ Nội vụ đổi lại tên thành Bộ Công an.[9]

Ngày 9 tháng 6 năm 1998, Thủ tướng Chính phủ ký Nghị định số 37/1998/NĐ-CP, Quy định chức năng nhiệm vụ quyền hạn và cơ cấu tổ chức của Bộ Công an.[10]

Ngày 5 tháng 8 năm 2002, Quốc hội ra Nghị quyết số 02/2002/QH11 về việc quy định danh sách các bộ và cơ quan ngang bộ của Chính phủ. Theo đó, Bộ Nội vụ mới được thành lập trên cơ sở đổi tên từ Ban Tổ chức Cán bộ Chính phủ và tồn tại song song với Bộ Công an.[11]

Ngày 14 tháng 11 năm 2003, Thủ tướng Chính phủ ký Nghị định số 136/2003/NĐ-CP, Quy định chức năng nhiệm vụ quyền hạn và cơ cấu tổ chức của Bộ Công an[12]

Ngày 15 tháng 9 năm 2009, Thủ tướng Chính phủ ký Nghị định số 77/2009/NĐ-CP, Quy định chức năng nhiệm vụ quyền hạn và cơ cấu tổ chức của Bộ Công an. Theo đó, 6 Tổng cục hiện tại của Bộ Công an (An ninh nhân dân, Cảnh sát nhân dân, Xây dựng Lực lượng, Hậu cần, Tình báo, Kỹ thuật) được tách, sáp nhập và đổi tên thành 8 Tổng cục đó là (An ninh 1, An ninh 2, Xây dựng Lực lượng, Hậu cần - Kỹ thuật, Tình báo, Cảnh sát Phòng chống tội phạm, Cảnh sát Quản lý hành chính về trật tự an toàn xã hội, Cảnh sát Thi hành án hình sự và Hỗ trợ tư pháp).

Ngày 9 tháng 12 năm 2013, Ban Bí thư Trung ương Đảng (khóa XI) đã ban hành Quy định số 216-QĐ/TW về thực hiện chế độ chính ủy, chính trị viên ở Bộ Tư lệnh Cảnh sát cơ động, Bộ Công an[13]

Ngày 17 tháng 11 năm 2014, Thủ tướng Chính phủ ký Nghị định số 106/2014/NĐ-CP, Quy định chức năng nhiệm vụ quyền hạn và cơ cấu tổ chức của Bộ Công an và có hiệu lực từ 01/01/2015. Theo đó, 8 Tổng cục (An ninh 1, An ninh 2, Xây dựng Lực lượng, Hậu cần Kỹ thuật, Tình báo, Cảnh sát Phòng chống tội phạm, Cảnh sát Quản lý hành chính về trật tự an toàn xã hội, Cảnh sát Thi hành án và Hỗ trợ tư pháp) được sáp nhập lại thành 6 Tổng cục (An ninh, Chính trị, Hậu cần - Kỹ thuật, Tình báo, Cảnh sát và Cảnh sát thi hành án hình sự và Hỗ trợ tư pháp). Cũng theo đó, Tổng cục Xây dựng Lực lượng được đổi tên thành Tổng cục Chính trị Công an nhân dân.[14][15][16][17][18]

Trước ngày 6 tháng 8 năm 2018, Bộ Công an gồm có 6 Tổng cục là Tổng cục An ninh (Tổng cục I), Tổng cục Cảnh sát (Tổng cục II), Tổng cục Chính trị (Tổng cục III), Tổng cục Hậu cần - Kỹ thuật (Tổng cục IV), Tổng cục Tình báo (Tổng cục V), Tổng cục Cảnh sát Thi hành án hình sự và Hỗ trợ tư pháp (Tổng cục VIII). Các Tổng cục VI (Tổng cục Cảnh sát Phòng chống Tội phạm) và Tổng cục VII (Tổng cục Cảnh sát Quản lý Hành chính về trật tự an toàn xã hội) đã sáp nhập vào Tổng cục Cảnh sát.

Ngày 6 tháng 8 năm 2018, Thủ tướng Chính phủ Việt Nam Nguyễn Xuân Phúc đã ký ban hành Nghị định 01 có hiệu lực cùng ngày quy định chức năng nhiệm vụ, quyền hạn và cơ cấu tổ chức của Bộ Công an, theo đó Bộ Công an không còn cấp Tổng cục.[19] Bộ máy Bộ Công an giảm 6 tổng cục và gần 60 đơn vị cấp Cục, 300 đơn vị cấp Phòng.[20] Bộ máy công an địa phương giảm hơn 500 đơn vị cấp phòng và 1000 đơn vị cấp Đội.[21] Sở Cảnh sát phòng cháy và chữa cháy của 20 tỉnh thành gồm Hà Nội, Thành phố Hồ Chí Minh, Hải Phòng, Đà Nẵng, Cần Thơ, Thái Nguyên, Vĩnh Phúc, Bắc Ninh, Quảng Ninh, Thanh Hóa, Nghệ An, Thừa Thiên Huế, Quảng Ngãi, Bình Định, Khánh Hòa, Đắk Lắk, Lâm Đồng, Bình Dương, Đồng Nai, Bà Rịa - Vũng Tàu được sáp nhập vào Công an tỉnh, thành phố tương ứng.[22] Cục Cảnh sát điều tra về tội phạm kinh tế, tham nhũng sáp nhập với Cục Cảnh sát điều tra tội phạm buôn lậu thành Cục Cảnh sát điều tra tội phạm về tham nhũng, kinh tế, buôn lậu. Cục An ninh mạng trực thuộc Bộ Công an và Cục Cảnh sát phòng chống tội phạm sử dụng công nghệ cao thuộc Tổng cục cảnh sát sáp nhập thành Cục An ninh mạng và phòng, chống tội phạm sử dụng công nghệ cao trực thuộc Bộ Công an Việt Nam.[23][24] Cục An ninh Thông tin truyền thông sáp nhập vào Cục An ninh chính trị nội bộ.[25]